1. Field of the Invention
The present invention relates generally to an improved data processing system and in particular to the compilation of computer usable program code. Still more particularly, the present invention relates to diagnosing alias violations in memory access commands during an optimizing compilation process.
2. Description of the Related Art
Compilers are software programs used to translate program instructions written in a source language to equivalent program instructions written in a target language. The source language is a high-level language designed to be interpreted by humans, the target language is usually a low-level language suitable for execution by computer hardware. Thus, the compiler is said to compile the source code into executable code.
Optimizing compilers are used to improve the quality of the program instruction generated without changing the intended meaning of the source code. For example, an optimizing compiler can reduce the time required to execute the program instructions or the memory footprint of the resulting program. During the optimization process, the source code is often re-ordered so that commands are executed more efficiently.
In the process of translating source code to target code, compilers routinely reorder program instructions to improve the runtime performance of the generated target code. Because instruction reordering may not preserve the original semantics of a program, a compiler must determine that reordered instructions do not reference the same or overlapping memory regions before reordering can be performed. For example, a store instruction can be safely moved prior to a subsequent load instruction if the compiler can determine that the memory region to which the store instruction writes and the memory region which is read by the load instruction do not overlap. If the instructions do reference the same memory region, then reordering could cause the reordered program to perform incorrectly. For example, reordering could cause a new value to be stored in memory before an instruction to load from the same memory is executed, when the value expected to be loaded was the older value (i.e., before the older value was overwritten by the new value). However, some reordered instructions may reference the same memory region. Additionally, two load instructions referencing the same memory region can be freely interchanged, or reordered, if no intervening store instruction to that memory region exists.
A memory region refers to a memory address and size which defines a contiguous block of memory. A read or write instruction to a memory region may be referred to as a memory access. In the context of this application an indirect memory access command or reference refers to one of a set of memory regions and a direct memory access command or reference refers to a single memory region.
Two or more memory accesses which refer to memory regions which overlap are said to alias one another. The presence of aliasing limits the amount of reordering a compiler can safely perform. The alias set of a memory access in a program is the set of the other memory accesses in that program which may refer to a memory region which overlaps with the memory region referred to by that memory access.
A compiler does not always detect all problems that can be caused by aliasing. Determining all possible aliasing relationship in a program is often computationally intractable. Therefore, programming languages have established rules, known as alias rules, which describe which memory references may alias one another. Additionally, compilers often allow the user to choose an alias rule to which the source program must conform. Thus, an alias rule represents a “contract” between the programmer and the compiler. If the program being compiled does not conform to the chosen alias rule, then the compiler might optimize the program in such a way as to modify the original semantics, or meaning, of the program.
Furthermore, aliasing violations often prove costly as unexpected program behavior may only appear at the highest levels of optimization, or in time as code optimizers evolve and take advantage of previously unexploited opportunities. The term highest optimization levels refer to a highest degree of code rearrangement performed by a compiler to maximize efficiency of the resulting executable code.